1. Field of Invention
This invention pertains to error correction systems for the correction of data, and particularly to circuitry for performing mathematical operations involved in such error correction.
2. Related Art and Other Considerations
Error correction operations are typically conducted in a plurality of bases of representation .alpha. basis representation and/or .beta. basis representation) and often involve considerably more than generation of polynonmial coefficients. Indeed, in addition to basis conversions (e.g., either from .alpha. basis representation to .beta. basis representation or vise-versa), other operations--including multiplication, inversion, and addition operations--are often conducted.
While conventional error correction circuits, including Berlekamp-Massey-type convolution circuits, primarily operate in a parallel data transfer mode, it has been recognized that the serial transfer of data significantly reduces circuit size (e.g., by the avoidance of parallel buses) and thus reduces circuit cost. Yet heretofore there has been lacking a circuit which executes numerous mathematical serial operations, including basis conversion, inner product generation, multiplication, inversion, and addition operations.
One example wherein error correction operations are performed is a compact disk (CD) drive. Compact disks (CDs) were initially used for audio recording and reproduction. Manipulation of CDs by a CD drive for audio purposes does not involve random access, and any searching (e.g., for different audio works recorded on the disk) occurs at a relatively slow speed. Moreover, since the human ear processes and receives reproduced audio in a continuous, essentially real-time manner, for audio purposes it is not necessary for CD drives to correct all errors. If an uncorrectable error occurs in audio recording, it is not practical to back up and re-read the portion of the CD where the error resides in an attempt to correct the error. Instead, any uncorrectable error is typically blanked out and/or replaced with a signal deduced (e.g., averaged) with other time-proximate signals.
Recording on a CD occurs in an essentially spiral path, the path being conceptualized to some extent as having tracks of different radii. For audio use CDs are formatted to contain a plurality of frames. Each frame has 2352 8-bit bytes of digital audio data.
For audio use, CDs are formatted to contain not only digital audio data for the works (e.g., songs) recorded thereon, but also subcodes. The subcodes are dispersed amongst the audio data on the CD at regular intervals. The dispersed subcodes are assembled for grouping into packs. As shown in FIG. 8A, each subcode pack has 24 6-bit bytes. Thus, the field length (6 bits) of each subcode byte differs from the field length (8 bits) of the data bytes.
As shown in FIG. 8A, a subcode pack is conceptualized as being divided into a "Q" part and a "P" part. The "Q" part of each subcode pack consists of the first four 6-bit symbols (e.g., bytes 0-3); the "P" part of each subcode pack consists of the remaining symbols (bytes 4-23). Although not necessary for an understanding of the present invention, it is mentioned in passing that subcodes are utilized to provide such indications as when a track is switched, whether a track is audio data or not, the length of time since the beginning of the work, etc. In some applications, graphical information for visual display information for accompanying the audio output (e.g., karaote) can be stored in the subcodes.
Although initially used for audio purposes, in more recent years CDs have also been used for recording computer data. From the perspective of computer data, the CD is formatted to include a plurality of 2352 8-bit bytes. Subcodes are not utilized with computer data recorded on CD.
When a CD is being reproduced, pertinent portions of a frame (for audio) or sector (for computer data) are loaded into a buffer (e.g., RAM). The buffer holds 2064 bytes of data for each frame/sector.
All CD data is protected at the lowest level by the CIRC ECC. In connection with recording/reproducing computer data, some CD systems provide additional error correction capability called layered ECC. For purposes of performing error correction, as stored in the buffer each frame/sector is conceptualized as comprising two blocks or interleaves. FIG. 8B shows both an even block/interleave and an odd block/interleave for a frame/sector. The two blocks of a frame/sector are operated upon by error correction codes using a scheme of product codes. In each block, a column of bytes comprises a codeword. For example, in the even block, bytes 0000, 0043, 0086, . . . , 0989 comprise a data portion of column codeword CWeven.sub.0 ; bytes 0001, 0044, 0087, . . . , 0990 comprise a data portion of column codeword CWeven.sub.1 ; and so forth. Bytes 1032 and 1075 comprise an ECC portion of column codeword CWeven.sub.0 ; bytes 1033 and 1076 comprise an ECC portion of column codeword CWeven.sub.1 ; and so forth. Similar codewords CWodd.sub.0, CWodd.sub.1, etc., exists for the odd block. Thus, there are forty-three column codewords for each block. The last two bytes of each block (e.g., bytes 1030.sub.even ; 1030.sub.odd ; 1031.sub.even ; 1031.sub.odd) contain CRC/EDC information and accordingly are known as EDC or CRC blocks. In some formats the CRC bytes are not necessarily the last bytes of the data portion of a block. For example, data formats which do not completely fill the blocks of FIG. 2 can place the CRC bytes following the end of data and follow the CRC bytes with pad bytes of zeros until the blocks are filled.
Also in each block, a diagonal line of bytes comprises a diagonal codeword. For example, with reference to the even block of FIG. 8B, a first diagonal codeword includes bytes 0000, 0044, 0088, . . . 1056, 1100, 0026, . . . 0686, 0730, 1118, 1144. Thus, there are forty-two column codewords and twenty-six diagonal codewords for each block.
The illustration of FIG. 8B should not obscure the fact that the data in the buffer is not stored in codeword order. For example, a sector in the buffer has bytes stored in the following order: byte 0000 of the even block (i.e., byte 0000.sub.even); byte 0000 from the odd block (i.e., byte 0000.sub.odd); byte 0001.sub.even ; byte 0001.sub.odd ; and so forth continuing to byte 1031.sub.even, 1031.sub.odd.
When computer data has been received from a CD by a system having error correction capability, the CIRC ECC may generate error pointers to be used by the layered ECC. In such error correction systems for CD drives, up to two pointers are supplied for each codeword. Each pointer is usually one bit of information. Typically pointer information for a sector is stored in the buffer either before or after its associated sector, and in such a manner that it can be determined to which byte of which codeword the pointer refers.
Thus, for computer data purposes, the buffer for the CD system has stored a plurality of sectors, with pointer information also being stored therein for each sector. Similarly, for audio purposes, the buffer of the CD system has stored therein a plurality of frames, as well as a plurality of packs of subcodes.